package wtx.leetcode;

import java.util.*;
import java.util.Random;

/**
 * Given an array nums of n integers, are there elements a, b, c in nums such
 * that a + b + c = 0 ? Find all unique triplets in the array which gives the sum
 * of zero.
 * 
 * Note:
 * 
 * The solution set must not contain duplicate triplets.
 * 
 * Example:
 * 
 * Given array nums = [-1, 0, 1, 2, -1, -4],
 * 
 * A solution set is: [ 
 *        [-1, 0, 1], 
 *        [-1, -1, 2] 
 * ]
 * 
 *  first sort:
 *   [-4, -1, -1, 0, 1, 2]
 *  start from first two element: 
 *     init: first = 0, second = 1, last = 5
 *     sum(0, second) is the smallest sum, so the 3rd element must lie at the last, 
 *      start from last, 
 *        if sum(first, second, last) == 0, we find a tuple, if this is not recored before, record it;
 *        else: change second = second + 1
 *        finally: last --,
 *        if second >= last: first = first + 1
 *        if first >= last: end
 *
 *  solution2:
 *    tripCache = set[long]
 *    for first in 0 ... last-1:
 *      for second in first+1 ... last:
 *        key = {first, second}
 *        cache.add[sum, {key, (first, second)}]
 *    for i in 0 ... last:
 *      int target = -nums[i]
 *      if target in cache:
 *        for key in cacke[target]:
 *          if key not in tripCache:
 *            ret.add({nums[i], }) 
 */
class Solution {
  private static long LONG_MASK = 0x00000000ffffffffl;

  private static long getKey(int f, int s) {
    return ((0L | f) << 32) | (LONG_MASK & s);
  }
  public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    if (nums == null || nums.length < 3) {
      return ret;
    }
    Set<Long> tripletSet = new HashSet<>();
    Arrays.sort(nums);
    HashMap<Integer, Integer> elemPosMap = new HashMap<>();
    for (int i = 0; i < nums.length; ++i) {
      elemPosMap.put(nums[i], i);
    }
    for (int i = 0; i < nums.length - 2; ++i) {
      if (nums[i] > 0) break;
      for (int j = i + 1; j < nums.length; ++j) {
        int target = - nums[i] - nums[j];
        if (target < 0) break;
        Integer pos = elemPosMap.get(target);
        if (pos != null && pos > j) {
          long key = getKey(nums[i], nums[j]);
          if (!tripletSet.contains(key)) {
            tripletSet.add(key);
            List<Integer> tri = new ArrayList<>();
            tri.add(nums[i]);
            tri.add(nums[j]);
            tri.add(target);
            ret.add(tri);
          } 
        }
      }
    }
    return ret;
  }
  public static void benchMark() {
    long alltime = 0;
    long maxtime = 0;
    int[] maxnums = null;
    for (int k = 0; k < 5000; ++k) {
      final int NUM_LEN = 100;
      final int NUM_BOUND = 100;
      int[] nums = new int[NUM_LEN];
      Random rnd = new Random(1234 + k);
      nums[0] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
      System.out.print("[" + nums[0]);
      for (int i = 1; i < NUM_LEN; ++i) {
        nums[i] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
        if (i < 5) {
          System.out.print(", " + nums[i]);
        }
      }
      System.out.println("... ]");
      Solution s = new Solution();
      // List<List<Integer>> ret = 
      s.threeSum(nums);
      long curt = System.currentTimeMillis();
      for (int n = 0; n < 100; ++n) {
        s.threeSum(nums);
      }
      long e = System.currentTimeMillis() - curt;
      alltime += e;
      if (e > maxtime) {
        maxtime = e;
        maxnums = nums;
      }
      System.out.println(e + " ms");
    }
    System.out.println("\nall eclipse time: " + alltime);
    System.out.print("[" + maxnums[0]);
    for (int i = 1; i < maxnums.length; ++i) {
      System.out.print(", " + maxnums[i]);
    }
    System.out.println("]\n eclipse time = " + maxtime);
  }

  public static void testOneCase() {
    // int[] nums = { -4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0 };
    // int[] nums = {-1, 0, 1, 0};
    // int[] nums = {-4, -1, -1, 0, 1, 2};
    // int[] nums = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
    final int NUM_LEN = 100;
    final int NUM_BOUND = 100;
    int[] nums = new int[NUM_LEN];
    Random rnd = new Random(1234 + 9);
    nums[0] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
    System.out.print("[" + nums[0]);
    for (int i = 1; i < NUM_LEN; ++i) {
      nums[i] = rnd.nextInt(2 * NUM_BOUND) - NUM_BOUND;
      if (i < 5) {
        System.out.print(", " + nums[i]);
      }
    }
    System.out.println("... ]");
    Solution s = new Solution();
    // List<List<Integer>> ret =
    s.threeSum(nums);
    long curt = System.currentTimeMillis();
    for (int n = 0; n < 100; ++n) {
      s.threeSum(nums);
    }
    long e = System.currentTimeMillis() - curt;
    System.out.println(e + " ms");
    // for (List<Integer> tri : ret) {
    //   System.out.print("[" + tri.get(0));
    //   for (int i = 1; i < 3; ++i) {
    //     System.out.print(", " + tri.get(i));
    //   }
    //   System.out.println("]");
    // }
  }
  public static void main(String[] args) {
    benchMark();
    // testOneCase();
  }
}